home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 001-025 / disk_010 / sq.usq / sq.c < prev    next >
C/C++ Source or Header  |  1992-05-06  |  29KB  |  887 lines
  1.  
  2. /* This program compresses a file without loosing information.
  3.  * The "usq" program is required to unsqueeze the file
  4.  * before it can be used.
  5.  *
  6.  * Typical compression rates are between 30 and 50 percent for text files.
  7.  *
  8.  * Squeezing a really big file takes a few minutes.
  9.  *
  10.  * Useage:
  11.  *      sq [file1] [file2] ... [filen]
  12.  *
  13.  * where file1 through filen are the names of the files to be squeezed.
  14.  * The file type (under CP/M or MS-DOS) is changed to ".SQ"; under UN*X,
  15.  * ".SQ" is appended to the file name. The original file name is stored
  16.  * in the squeezed file.
  17.  *
  18.  * If no file name is given on the command line you will be
  19.  * prompted for commands (one at a time). An empty command
  20.  * terminates the program.
  21.  *
  22.  * The transformations compress strings of identical bytes and
  23.  * then encode each resulting byte value and EOF as bit strings
  24.  * having lengths in inverse proportion to their frequency of
  25.  * occurrance in the intermediate input stream. The latter uses
  26.  * the Huffman algorithm. Decoding information is included in
  27.  * the squeezed file, so squeezing short files or files with
  28.  * uniformly distributed byte values will actually increase size.
  29.  */
  30.  
  31. /* CHANGE HISTORY:
  32.  * 1.3  Close files properly in case of error exit.
  33.  * 1.4  Break up long introductory lines.
  34.  * 1.4  Send introduction only to console.
  35.  * 1.4  Send errors only to console.
  36.  * 1.5  Fix BUG that caused a rare few squeezed files
  37.  *      to be incorrect and fail the USQ crc check.
  38.  *      The problem was that some 17 bit codes were
  39.  *      generated but are not supported by other code.
  40.  *      THIS IS A MAJOR CHANGE affecting TR2.C and SQ.H and
  41.  *      requires recompilation of all files which are part
  42.  *      of SQ. Two basic changes were made: tree depth is now
  43.  *      used as a tie breaker when weights are equal. This
  44.  *      makes the tree shallower. Although that may always be
  45.  *      sufficient, an error trap was added to cause rescaling
  46.  *      of the counts if any code > 16 bits long is generated.
  47.  * 1.5  Add debugging displays option '-'.
  48.  * 1.6  Fixed to work correctly under MP/M II.  Also shortened
  49.  *      signon message.
  50.  * 2.0  New version for use with CI-C86 compiler (CP/M-86 and MS-DOS)
  51.  * 2.1  Converted for use in MLINK
  52.  * 2.2  Converted for use with optimizing CI-C86 compiler (MS-DOS)
  53.  * 3.0  Generalized for UN*X use, changed output file naming convention
  54.  *
  55.  * 3.2  Ported to Amiga & Lattice C.  Combined all files
  56.  *      Rick Schaeffer [70120,174] 12/03/85
  57.  */
  58.  
  59. #include <stdio.h>
  60.  
  61. /* eject
  62. eject */
  63.  
  64. /*
  65.  * The following define MUST be set to the maximum length of a file name
  66.  * on the system "sq" is being compiled for.  If not, "sq" will not be
  67.  * able to check for whether the output file name it creates is valid
  68.  * or not.
  69.  */
  70.  
  71. #define FNM_LEN 35
  72. #define UNIX                            /* comment out for CP/M, MS-DOS versions */
  73.  
  74. #define VERSION "3.2   12/03/85"
  75.  
  76. /* Definitions and external declarations */
  77.  
  78. #define RECOGNIZE 0xFF76        /* unlikely pattern */
  79.  
  80. /* *** Stuff for first translation module *** */
  81.  
  82. #define DLE 0x90
  83.  
  84. unsigned int crc;        /* error check code */
  85.  
  86. /* *** Stuff for second translation module *** */
  87.  
  88. #define SPEOF 256       /* special endfile token */
  89. #define NUMVALS 257     /* 256 data values plus SPEOF*/
  90. /* Definitions and external declarations */
  91.  
  92.  char     debug;  /* Boolean flag */
  93.  
  94. /* *** Stuff for first translation module *** */
  95.  
  96.  int likect;      /*count of consecutive identical chars */
  97.  int lastchar, newchar;
  98.  char state;
  99.  
  100. /* states */
  101.  
  102. #define NOHIST  0       /*don't consider previous input*/
  103. #define SENTCHAR 1      /*lastchar set, no lookahead yet */
  104. #define SENDNEWC 2      /*newchar set, previous sequence done */
  105. #define SENDCNT 3       /*newchar set, DLE sent, send count next */
  106.  
  107. /* *** Stuff for second translation module *** */
  108.  
  109. #define NOCHILD -1      /* indicates end of path through tree */
  110. #define NUMNODES (NUMVALS + NUMVALS - 1)        /* nbr of nodes */
  111.  
  112. #define MAXCOUNT 0xFFFF /* biggest unsigned integer */
  113.  
  114. /* The following array of structures are the nodes of the
  115.  * binary trees. The first NUMVALS nodes becomethe leaves of the
  116.  * final tree and represent the values of the data bytes being
  117.  * encoded and the special endfile, SPEOF.
  118.  * The remaining nodes become the internal nodes of the final tree.
  119.  */
  120.  
  121.  struct   nd {
  122.         unsigned int weight;    /* number of appearances */
  123.         char tdepth;            /* length on longest path in tre*/
  124.         int lchild, rchild;     /* indexes to next level */
  125. } node[NUMNODES];
  126.  
  127.  int dctreehd;    /*index to head node of final tree */
  128.  
  129. /* This is the encoding table:
  130.  * The bit strings have first bit in  low bit.
  131.  * Note that counts were scaled so code fits unsigned integer
  132.  */
  133.  
  134.  char codelen[NUMVALS];           /* number of bits in code */
  135.  unsigned int code[NUMVALS];      /* code itself, right adjusted */
  136.  unsigned int tcode;              /* temporary code value */
  137.  
  138.  
  139. /* Variables used by encoding process */
  140.  
  141.  int curin;               /* Value currently being encoded */
  142.  char cbitsrem;           /* Number of code string bits remaining */
  143.  unsigned int ccode;      /* Current code shifted so next code bit is at right */
  144. #define ERROR -1
  145. #define TRUE 1
  146. #define FALSE 0
  147.  
  148. main(argc, argv)
  149. int argc;
  150. char *argv[];
  151. {
  152.         int i,c;
  153.         char inparg[128];       /* parameter from input */
  154.  
  155.         debug = FALSE;
  156.         printf("File squeezer version %s (original author: R. Greenlaw)\n\n", VERSION);
  157.  
  158.         /* Process the parameters in order */
  159.         for(i = 1; i < argc; ++i)
  160.                 obey(argv[i]);
  161.  
  162.         if(argc < 2) {
  163.                 printf("Enter file names, one line at a time, or type <RETURN> to quit.");
  164.                 do {
  165.                         printf("\n*");
  166.                         for(i = 0; i < 16; ++i) {
  167.                                 if((c = getchar()) == EOF)
  168.                                         c = '\n';       /* fake empty (exit) command */
  169.                                 if((inparg[i] = c) == '\n') {
  170.                                         inparg[i] = '\0';
  171.                                         break;
  172.                                 }
  173.                         }
  174.                         if(inparg[0] != '\0')
  175.                                 obey(inparg);
  176.                 } while(inparg[0] != '\0');
  177.         }
  178. }
  179.  
  180. /* eject
  181. eject */
  182.  
  183. obey(p)
  184. char *p;
  185. {
  186.         char *q;
  187.         char *rindex();
  188.         char outfile[128];      /* output file spec. */
  189.  
  190.         if(*p == '-') {
  191.                 /* toggle debug option */
  192.                 debug = !debug;
  193.                 return;
  194.         }
  195.  
  196.         /* Check for ambiguous (wild-card) name */
  197.         for(q = p; *q != '\0'; ++q)
  198.                 if(*q == '*' || *q == '?') {
  199.                         printf("\nAmbiguous name %s ignored\n", p);
  200.                         return;
  201.         }
  202.         /* First build output file name */
  203.         strcpy(outfile, p);             /* copy input name to output */
  204.  
  205.         /* Find and change output file suffix */
  206.  
  207.         if ((q = rindex(outfile, '.')) == NULL) /* if no '.' in name */
  208.                 strcat(outfile, ".qq");
  209.         else {
  210.                 strcat(q, "    ");              /* extend end of string marks */
  211.                 if (*++q == ' ')                /* if no next character */
  212.                         *q = 'q';
  213.                 *++q = 'q';                     /* make file .?q? */
  214.                 if (*++q == ' ')                /* if no next character */
  215.                         *q = '\0';              /*   terminate early */
  216.                 else
  217.                         *++q = '\0';            /* terminate filename */
  218.         }
  219.  
  220.         squeeze(p, outfile);
  221. }
  222.  
  223. /* eject
  224. eject */
  225.  
  226. squeeze(infile, outfile)
  227. char *infile, *outfile;
  228. {
  229.         int i, c,c2;
  230.         FILE *inbuff, *outbuff;         /* file buffers */
  231.         long    infilsiz;
  232.  
  233.  
  234.         printf("%s -> %s: ", infile, outfile);
  235.  
  236.         if(!(inbuff=fopen(infile, "rb"))) {
  237.                 printf("Can't open %s for input pass 1\n", infile);
  238.                 return;
  239.         }
  240.         if(!(outbuff=fopen(outfile, "wb"))) {
  241.                 printf("Can't create %s\n", outfile);
  242.                 fclose(inbuff);
  243.                 return;
  244.         }
  245.  
  246.         /* First pass - get properties of file */
  247.         crc = 0;        /* initialize checksum */
  248.         printf("analyzing, ");
  249.         init_ncr();
  250.         init_huff(inbuff);
  251.         infilsiz = ftell(inbuff);
  252.         fclose(inbuff);
  253.  
  254.         /* Write output file header with decoding info */
  255.         wrt_head(outbuff, infile);
  256.  
  257.         /* Second pass - encode the file */
  258.         printf("squeezing,");
  259.         if(!(inbuff=fopen(infile, "rb"))) {
  260.                 printf("Can't open %s for input pass 2\n", infile);
  261.                 goto closeout;
  262.         }
  263.         init_ncr();     /* For second pass */
  264.  
  265.         /* Translate the input file into the output file */
  266.         while((c = gethuff(inbuff)) != EOF)
  267.                 putce(c, outbuff);
  268.         oflush(outbuff);
  269.         printf(" done.\n\t(%ld%% reduction.)\n",
  270.                 (infilsiz - ftell(outbuff))/(infilsiz / 100L));
  271. closeall:
  272.         fclose(inbuff);
  273. closeout:
  274.         fclose(outbuff);
  275. }
  276.  
  277. char *rindex(str,c)
  278. char  *str;
  279. char  c;
  280. {
  281.    int   i;
  282.  
  283.    for (i = strlen(str)-1; i >= 0; i--)
  284.       if (str[i] == c)
  285.          return(&str[i]);
  286.    return(NULL);
  287. }
  288.  
  289. /* First translation - encoding of repeated characters
  290.  * The code is byte for byte pass through except that
  291.  * DLE is encoded as DLE, zero and repeated byte values
  292.  * are encoded as value, DLE, count for count >= 3.
  293.  */
  294.  
  295. init_ncr()      /*initialize getcnr() */
  296. {
  297.         state = NOHIST;
  298. }
  299.  
  300. int
  301. getcnr(iob)
  302. FILE *iob;
  303. {
  304.         switch(state) {
  305.         case NOHIST:
  306.                 /* No relevant history */
  307.                 state = SENTCHAR;
  308.                 return lastchar = getc_crc(iob);
  309.         case SENTCHAR:
  310.                 /* Lastchar is set, need lookahead */
  311.                 switch(lastchar) {
  312.                 case DLE:
  313.                         state = NOHIST;
  314.                         return 0;       /* indicates DLE was the data */
  315.                 case EOF:
  316.                         return EOF;
  317.                 default:
  318.                         for(likect = 1; (newchar = getc_crc(iob)) == lastchar && likect < 255; ++likect)
  319.                                 ;
  320.                         switch(likect) {
  321.                         case 1:
  322.                                 return lastchar = newchar;
  323.                         case 2:
  324.                                 /* just pass through */
  325.                                 state = SENDNEWC;
  326.                                 return lastchar;
  327.                         default:
  328.                                 state = SENDCNT;
  329.                                 return DLE;
  330.                         }
  331.                 }
  332.         case SENDNEWC:
  333.                 /* Previous sequence complete, newchar set */
  334.                 state = SENTCHAR;
  335.                 return lastchar = newchar;
  336.         case SENDCNT:
  337.                 /* Sent DLE for repeat sequence, send count */
  338.                 state = SENDNEWC;
  339.                 return likect;
  340.         default:
  341.                 puts("Bug - bad state\n");
  342.                 exit(1);
  343.         }
  344. }
  345.  
  346. /******** Second translation - bytes to variable length bit strings *********/
  347.  
  348.  
  349. /* This translation uses the Huffman algorithm to develop a
  350.  * binary tree representing the decoding information for
  351.  * a variable length bit string code for each input value.
  352.  * Each string's length is in inverse proportion to its
  353.  * frequency of appearance in the incoming data stream.
  354.  * The encoding table is derived from the decoding table.
  355.  *
  356.  * The range of valid values into the Huffman algorithm are
  357.  * the values of a byte stored in an integer plus the special
  358.  * endfile value chosen to be an adjacent value. Overall, 0-SPEOF.
  359.  *
  360.  * The "node" array of structures contains the nodes of the
  361.  * binary tree. The first NUMVALS nodes are the leaves of the
  362.  * tree and represent the values of the data bytes being
  363.  * encoded and the special endfile, SPEOF.
  364.  * The remaining nodes become the internal nodes of the tree.
  365.  *
  366.  * In the original design it was believed that
  367.  * a Huffman code would fit in the same number of
  368.  * bits that will hold the sum of all the counts.
  369.  * That was disproven by a user's file and was a rare but
  370.  * infamous bug. This version attempts to choose among equally
  371.  * weighted subtrees according to their maximum depths to avoid
  372.  * unnecessarily long codes. In case that is not sufficient
  373.  * to guarantee codes <= 16 bits long, we initially scale
  374.  * the counts so the total fits in an unsigned integer, but
  375.  * if codes longer than 16 bits are generated the counts are
  376.  * rescaled to a lower ceiling and code generation is retried.
  377.  */
  378.  
  379. /* Initialize the Huffman translation. This requires reading
  380.  * the input file through any preceding translation functions
  381.  * to get the frequency distribution of the various values.
  382.  */
  383.  
  384. init_huff(ib)
  385. FILE *ib;
  386. {
  387.         int c, i;
  388.         int btlist[NUMVALS];    /* list of intermediate binary trees */
  389.         int listlen;            /* length of btlist */
  390.         unsigned int *wp;       /* simplifies weight counting */
  391.         unsigned int ceiling;   /* limit for scaling */
  392.  
  393.         /* Initialize tree nodes to no weight, no children */
  394.         init_tree();
  395.  
  396.         /* Build frequency info in tree */
  397.         do {
  398.                 c = getcnr(ib);
  399.                 if(c == EOF)
  400.                         c = SPEOF;
  401.                 if(*(wp = &node[c].weight) !=  MAXCOUNT)
  402.                         ++(*wp);
  403.         } while(c != SPEOF);
  404. #ifdef DEBUG
  405.         pcounts();      /* debugging aid */
  406. #endif
  407.         ceiling = MAXCOUNT;
  408.  
  409.         do {    /* Keep trying to scale and encode */
  410.                 if(ceiling != MAXCOUNT)
  411.                         printf("*** rescaling ***, ");
  412.                 scale(ceiling);
  413.                 ceiling /= 2;   /* in case we rescale */
  414. #ifdef DEBUG
  415.                 pcounts();      /* debugging aid */
  416. #endif
  417.  
  418.                 /* Build list of single node binary trees having
  419.                  * leaves for the input values with non-zero counts
  420.                  */
  421.                 for(i = listlen = 0; i < NUMVALS; ++i)
  422.                         if(node[i].weight != 0) {
  423.                                 node[i].tdepth = 0;
  424.                                 btlist[listlen++] = i;
  425.                         }
  426.  
  427.                 /* Arrange list of trees into a heap with the entry
  428.                  * indexing the node with the least weight at the top.
  429.                  */
  430.                 heap(btlist, listlen);
  431.  
  432.                 /* Convert the list of trees to a single decoding tree */
  433.                 bld_tree(btlist, listlen);
  434.  
  435.                 /* Initialize the encoding table */
  436.                 init_enc();
  437.  
  438.                 /* Try to build encoding table.
  439.                  * Fail if any code is > 16 bits long.
  440.                  */
  441.         } while(buildenc(0, dctreehd) == ERROR);
  442. #ifdef DEBUG
  443.         phuff();        /* debugging aid */
  444. #endif
  445.         /* Initialize encoding variables */
  446.         cbitsrem = 0;   /*force initial read */
  447.         curin = 0;      /*anything but endfile*/
  448. }
  449. /* ^L */
  450. /* The count of number of occurrances of each input value
  451.  * have already been prevented from exceeding MAXCOUNT.
  452.  * Now we must scale them so that their sum doesn't exceed
  453.  * ceiling and yet no non-zero count can become zero.
  454.  * This scaling prevents errors in the weights of the
  455.  * interior nodes of the Huffman tree and also ensures that
  456.  * the codes will fit in an unsigned integer. Rescaling is
  457.  * used if necessary to limit the code length.
  458.  */
  459.  
  460. scale(ceil)
  461. unsigned int ceil;      /* upper limit on total weight */
  462. {
  463.         int c, ovflw, divisor, i;
  464.         unsigned int w, sum;
  465.         char increased;         /* flag */
  466.  
  467.         do {
  468.                 for(i = sum = ovflw = 0; i < NUMVALS; ++i) {
  469.                         if(node[i].weight > (ceil - sum))
  470.                                 ++ovflw;
  471.                         sum += node[i].weight;
  472.                 }
  473.  
  474.                 divisor = ovflw + 1;
  475.  
  476.                 /* Ensure no non-zero values are lost */
  477.                 increased = FALSE;
  478.                 for(i = 0; i < NUMVALS; ++i) {
  479.                         w = node[i].weight;
  480.                         if (w < divisor && w > 0) {
  481.                                 /* Don't fail to provide a code if it's used at all */
  482.                                 node[i].weight = divisor;
  483.                                 increased = TRUE;
  484.                         }
  485.                 }
  486.         } while(increased);
  487.  
  488.         /* Scaling factor choosen, now scale */
  489.         if(divisor > 1)
  490.                 for(i = 0; i < NUMVALS; ++i)
  491.                         node[i].weight /= divisor;
  492. }
  493. /* ^L */
  494. /* heap() and adjust() maintain a list of binary trees as a
  495.  * heap with the top indexing the binary tree on the list
  496.  * which has the least weight or, in case of equal weights,
  497.  * least depth in its longest path. The depth part is not
  498.  * strictly necessary, but tends to avoid long codes which
  499.  * might provoke rescaling.
  500.  */
  501.  
  502. heap(list, length)
  503. int list[], length;
  504. {
  505.         int i;
  506.  
  507.         for(i = (length - 2) / 2; i >= 0; --i)
  508.                 adjust(list, i, length - 1);
  509. }
  510.  
  511. /* Make a heap from a heap with a new top */
  512.  
  513. adjust(list, top, bottom)
  514. int list[], top, bottom;
  515. {
  516.         int k, temp;
  517.         char cmptrees();
  518.  
  519.         k = 2 * top + 1;        /* left child of top */
  520.         temp = list[top];       /* remember root node of top tree */
  521.         if( k <= bottom) {
  522.                 if( k < bottom && cmptrees(list[k], list[k + 1]))
  523.                         ++k;
  524.  
  525.                 /* k indexes "smaller" child (in heap of trees) of top */
  526.                 /* now make top index "smaller" of old top and smallest child */
  527.                 if(cmptrees(temp, list[k])) {
  528.                         list[top] = list[k];
  529.                         list[k] = temp;
  530.                         /* Make the changed list a heap */
  531.                         adjust(list, k, bottom); /*recursive*/
  532.                 }
  533.         }
  534. }
  535.  
  536. /* Compare two trees, if a > b return true, else return false
  537.  * note comparison rules in previous comments.
  538.  */
  539.  
  540. char    /* Boolean */
  541. cmptrees(a, b)
  542. int a, b;       /* root nodes of trees */
  543. {
  544.         if(node[a].weight > node[b].weight)
  545.                 return TRUE;
  546.         if(node[a].weight == node[b].weight)
  547.                 if(node[a].tdepth > node[b].tdepth)
  548.                         return TRUE;
  549.         return FALSE;
  550. }
  551. /* ^L */
  552. /* HUFFMAN ALGORITHM: develops the single element trees
  553.  * into a single binary tree by forming subtrees rooted in
  554.  * interior nodes having weights equal to the sum of weights of all
  555.  * their descendents and having depth counts indicating the
  556.  * depth of their longest paths.
  557.  *
  558.  * When all trees have been formed into a single tree satisfying
  559.  * the heap property (on weight, with depth as a tie breaker)
  560.  * then the binary code assigned to a leaf (value to be encoded)
  561.  * is then the series of left (0) and right (1)
  562.  * paths leading from the root to the leaf.
  563.  * Note that trees are removed from the heaped list by
  564.  * moving the last element over the top element and
  565.  * reheaping the shorter list.
  566.  */
  567.  
  568. bld_tree(list, len)
  569. int list[];
  570. int len;
  571. {
  572.         int freenode;           /* next free node in tree */
  573.         int lch, rch;           /* temporaries for left, right children */
  574.         struct nd *frnp;        /* free node pointer */
  575.         int i;
  576.         char maxchar();
  577.  
  578.         /* Initialize index to next available (non-leaf) node.
  579.          * Lower numbered nodes correspond to leaves (data values).
  580.          */
  581.         freenode = NUMVALS;
  582.  
  583.         while(len > 1) {
  584.                 /* Take from list two btrees with least weight
  585.                  * and build an interior node pointing to them.
  586.                  * This forms a new tree.
  587.                  */
  588.                 lch = list[0];  /* This one will be left child */
  589.  
  590.                 /* delete top (least) tree from the list of trees */
  591.                 list[0] = list[--len];
  592.                 adjust(list, 0, len - 1);
  593.  
  594.                 /* Take new top (least) tree. Reuse list slot later */
  595.                 rch = list[0];  /* This one will be right child */
  596.  
  597.                 /* Form new tree from the two least trees using
  598.                  * a free node as root. Put the new tree in the list.
  599.                  */
  600.                 frnp = &node[freenode]; /* address of next free node */
  601.                 list[0] = freenode++;   /* put at top for now */
  602.                 frnp->lchild = lch;
  603.                 frnp->rchild = rch;
  604.                 frnp->weight = node[lch].weight + node[rch].weight;
  605.                 frnp->tdepth = 1 + maxchar(node[lch].tdepth, node[rch].tdepth);
  606.                 /* reheap list  to get least tree at top*/
  607.                 adjust(list, 0, len - 1);
  608.         }
  609.         dctreehd = list[0];     /*head of final tree */
  610. }
  611. /* ^L */
  612. char
  613. maxchar(a, b)
  614. char a, b;
  615. {
  616.         return a > b ? a : b;
  617. }
  618. /* Initialize all nodes to single element binary trees
  619.  * with zero weight and depth.
  620.  */
  621.  
  622. init_tree()
  623. {
  624.         int i;
  625.  
  626.         for(i = 0; i < NUMNODES; ++i) {
  627.                 node[i].weight = 0;
  628.                 node[i].tdepth = 0;
  629.                 node[i].lchild = NOCHILD;
  630.                 node[i].rchild = NOCHILD;
  631.         }
  632. }
  633.  
  634. init_enc()
  635. {
  636.         int i;
  637.  
  638.         /* Initialize encoding table */
  639.         for(i = 0; i < NUMVALS; ++i) {
  640.                 codelen[i] = 0;
  641.         }
  642. }
  643. /* ^L */
  644. /* Recursive routine to walk the indicated subtree and level
  645.  * and maintain the current path code in bstree. When a leaf
  646.  * is found the entire code string and length are put into
  647.  * the encoding table entry for the leaf's data value.
  648.  *
  649.  * Returns ERROR if codes are too long.
  650.  */
  651.  
  652. int             /* returns ERROR or NULL */
  653. buildenc(level, root)
  654. int level;/* level of tree being examined, from zero */
  655. int root; /* root of subtree is also data value if leaf */
  656. {
  657.         int l, r;
  658.  
  659.         l = node[root].lchild;
  660.         r = node[root].rchild;
  661. #ifdef DEBUG
  662.         if (debug) printf("level=%d,root=%d,l=%d,r=%d,tcode=%04x\n",level,root,l,r,tcode);
  663. #endif
  664.         if( l == NOCHILD && r == NOCHILD) {
  665.                 /* Leaf. Previous path determines bit string
  666.                  * code of length level (bits 0 to level - 1).
  667.                  * Ensures unused code bits are zero.
  668.                  */
  669.                 codelen[root] = level;
  670.                 code[root] = tcode & ((unsigned int)(~0) >> ((sizeof(int) * 8) - level));
  671. #ifdef DEBUG
  672.                 if (debug) printf("  codelen[%d]=%d,code[%d]=%02x\n",root,codelen[root],root,code[root]);
  673. #endif
  674.                 return( (level > 16) ? ERROR : 0);
  675.         } else {
  676.                 if( l != NOCHILD) {
  677.                         /* Clear path bit and continue deeper */
  678.                         tcode &= ~(1 << level);
  679.                         /* NOTE RECURSION */
  680.                         if(buildenc(level + 1, l) == ERROR)
  681.                                 return ERROR;
  682.                 }
  683.                 if(r != NOCHILD) {
  684.                         /* Set path bit and continue deeper */
  685.                         tcode |= 1 << level;
  686.                         /* NOTE RECURSION */
  687.                         if(buildenc(level + 1, r) == ERROR)
  688.                                 return ERROR;
  689.                 }
  690.         }
  691.         return NULL;    /* if we got here we're ok so far */
  692. }
  693. /* ^L */
  694. /* Write out the header of the compressed file */
  695.  
  696. wrt_head(ob, infile)
  697. FILE *ob;
  698. char *infile;   /* input file name (w/ or w/o drive) */
  699. {
  700.         int i, k, l, r;
  701.         int numnodes;           /* nbr of nodes in simplified tree */
  702.  
  703.         putwe(RECOGNIZE, ob);   /* identifies as compressed */
  704.         putwe(crc, ob);         /* unsigned sum of original data */
  705.  
  706.         /* Record the original file name w/o drive */
  707.         if(*(infile + 1) == ':')
  708.                 infile += 2;    /* skip drive */
  709.  
  710.         do {
  711.                 putce(*infile, ob);
  712.         } while(*(infile++) != '\0');
  713.  
  714.  
  715.         /* Write out a simplified decoding tree. Only the interior
  716.          * nodes are written. When a child is a leaf index
  717.          * (representing a data value) it is recoded as
  718.          * -(index + 1) to distinguish it from interior indexes
  719.          * which are recoded as positive indexes in the new tree.
  720.          * Note that this tree will be empty for an empty file.
  721.          */
  722.  
  723.         numnodes = dctreehd < NUMVALS ? 0 : dctreehd - (NUMVALS -1);
  724.         putwe(numnodes, ob);
  725.  
  726.         for(k = 0, i = dctreehd; k < numnodes; ++k, --i) {
  727.                 l = node[i].lchild;
  728.                 r = node[i].rchild;
  729.                 l = l < NUMVALS ? -(l + 1) : dctreehd - l;
  730.                 r = r < NUMVALS ? -(r + 1) : dctreehd - r;
  731.                 putwe(l, ob);   /* left child */
  732.                 putwe(r, ob);   /* right child */
  733.         }
  734. }
  735. /* ^L */
  736. /* Get an encoded byte or EOF. Reads from specified stream AS NEEDED.
  737.  *
  738.  * There are two unsynchronized bit-byte relationships here.
  739.  * The input stream bytes are converted to bit strings of
  740.  * various lengths via the static variables named c...
  741.  * These bit strings are concatenated without padding to
  742.  * become the stream of encoded result bytes, which this
  743.  * function returns one at a time. The EOF (end of file) is
  744.  * converted to SPEOF for convenience and encoded like any
  745.  * other input value. True EOF is returned after that.
  746.  *
  747.  * The original gethuff() called a seperate function,
  748.  * getbit(), but that more readable version was too slow.
  749.  */
  750.  
  751. int                             /*  Returns byte values except for EOF */
  752. gethuff(ib)
  753. FILE *ib;
  754. {
  755.         unsigned int rbyte;     /* Result byte value */
  756.         char need, take;        /* numbers of bits */
  757.  
  758.         rbyte = 0;
  759.         need = 8;               /* build one byte per call */
  760.  
  761.         /* Loop to build a byte of encoded data
  762.          * Initialization forces read the first time
  763.          */
  764.  
  765. loop:
  766.         if(cbitsrem >= need) {
  767.                 /* Current code fullfills our needs */
  768.                 if(need == 0)
  769.                         return rbyte & 0xff;
  770.                 /* Take what we need */
  771.                 rbyte |= ccode << (8 - need);
  772.                 /* And leave the rest */
  773.                 ccode >>= need;
  774.                 cbitsrem -= need;
  775.                 return rbyte & 0xff;
  776.         }
  777.  
  778.         /* We need more than current code */
  779.         if(cbitsrem > 0) {
  780.                 /* Take what there is */
  781.                 rbyte |= ccode << (8 - need);
  782.                 need -= cbitsrem;
  783.         }
  784.         /* No more bits in current code string */
  785.         if(curin == SPEOF) {
  786.                 /* The end of file token has been encoded. If
  787.                  * result byte has data return it and do EOF next time
  788.                  */
  789.                 cbitsrem = 0;
  790.  
  791.                 return (need == 8) ? EOF : rbyte & 0xff;
  792.         }
  793.  
  794.         /* Get an input byte */
  795.         if((curin = getcnr(ib)) == EOF)
  796.                 curin = SPEOF;  /* convenient for encoding */
  797.  
  798.         /* Get the new byte's code */
  799.         ccode = code[curin];
  800.         cbitsrem = codelen[curin];
  801.  
  802.         goto loop;
  803. }
  804.  
  805.  
  806. /* Get next byte from file and update checksum */
  807.  
  808. int
  809. getc_crc(ib)
  810. FILE *ib;
  811. {
  812.         int c;
  813.  
  814.         c = getc(ib);
  815.         if (c != EOF)
  816.                 crc += c;               /* checksum */
  817.         return c;
  818. }
  819.  
  820. /* Output functions with error reporting */
  821.  
  822. static char obuf[128];
  823. static int oblen = 0;
  824.  
  825. putce(c,  iob)
  826. int c;
  827. FILE *iob;
  828. {
  829.         obuf[oblen++] = c;
  830.         if (oblen >= sizeof(obuf)) oflush(iob);
  831. }
  832.  
  833. putwe(w,  iob)
  834. int w;
  835. FILE *iob;
  836. {
  837.         obuf[oblen++] = w;
  838.         if (oblen >= sizeof(obuf)) oflush(iob);
  839.         obuf[oblen++] = w >> 8;
  840.         if (oblen >= sizeof(obuf)) oflush(iob);
  841. }
  842.  
  843. oflush(iob)                             /* flush output buffer */
  844. FILE *iob;
  845. {
  846.         if (oblen && !fwrite(obuf, oblen, 1, iob)) {
  847.                 printf("Error writing output file\n");
  848.                 exit(1);
  849.         }
  850.         oblen = 0;
  851. }
  852.  
  853. /* Debugging aids for SQ and related modules */
  854.  
  855. pcounts()
  856. {
  857.         int i;
  858.  
  859.         if(debug) {
  860.                 printf("\nCounts after 1st algorithm and maybe scaling");
  861.                 for(i = 0; i < NUMVALS; ++i) {
  862.                         if(i%8 == 0)
  863.                                 printf("\n%4x  ", i);
  864.                         printf("%5u  ", node[i].weight);
  865.                 }
  866.         printf("\n\n");
  867.         }
  868. }
  869.  
  870. phuff()
  871. {
  872.         int i;
  873.  
  874.         if(debug) {
  875.                 printf("\nEncoding tree - root=%3d\n", dctreehd);
  876.                 for(i = 0; i < NUMNODES; ++i)
  877.                         if(node[i].weight != 0)
  878.                                 printf("%3d  w=%5u d=%3d l=%3d r=%3d\n", i, node[i].weight, node[i].tdepth, node[i].lchild, node[i].rchild);
  879.  
  880.                 printf("\nHuffman codes\n");
  881.                 for(i = 0; i < NUMVALS; ++i) {
  882.                         if(codelen[i] > 0)
  883.                                 printf("%3d  %4x l=%2d c=%4x\n", i, i, codelen[i], code[i]);
  884.                 }
  885.         }
  886. }
  887.